package com.cat.dynamicPlanning;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/k-concatenation-maximum-sum/
 * @create 2025/8/29 20:47
 * @since JDK17
 */

public class Solution24 {
    static int N = ((int) (1e9 + 7));
    public long maxSubArray(int[] nums) {
        int n = nums.length;
        long ans = Math.max(nums[0], 0);
        long[] dp = new long[n];
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i] = nums[i] + Math.max(0, dp[i - 1]);
            ans = Math.max(dp[i], ans);
        }
        return ans % N;
    }
    public int kConcatenationMaxSum(int[] arr, int k) {
        int n = arr.length;
        long ans1 = maxSubArray(arr), sum = 0;
        if (k == 1) {
            return ((int) ans1);
        }
        int[] nums = new int[n * 2];
        for (int i = 0; i < n; i++) {
            nums[i] = nums[i + n] = arr[i];
            sum += arr[i];
        }
        long ans2 = maxSubArray(nums);   // 两个拼在一起
        if (ans1 >= ans2) {
            return ((int) ans1);
        } else {
            if (sum <= 0) {
                return ((int) ans2);
            } else {
                return ((int) ((ans2 + (k - 2) * sum) % N));
            }
        }
    }
}
